DC/LC analysis of Keccak-f[100]
Linear cryptanalysis

1 trails of length 2 read and checked.
1 trails of length 3 read and checked.
1 trails of length 4 read and checked.
1 trails of length 5 read and checked.
1 trails of length 6 read and checked.
Minimum weight: 8
       1 trails of weight  8
       1 trails of weight 20
       1 trails of weight 38
       1 trails of weight 66
       1 trails of weight 94

Showing the trails up to weight 94 (in no particular order).

2-round linear trail of total weight 8
* Profile related to χ:
Propagation weights:    4   4
Active rows:            2   2
* Profile related to θ:
Gaps:      5   0
Kernel:    N   k
Previous round would have weight at least 40
Round 0 (weight 4) after previous χ, then before θ of gap 5, then before χ (2 active rows):
X.XX.   X....   .XX..   XXXX.  |  .XX.X   .XXXX   ...XX   .X.X.  |  ....X   .....   .....   .....
X.XXX   ...X.   XX...   XX.XX  |  .XX..   .XXXX   ...XX   .X.X.  |  .....   .....   .....   .....
..X.X   .XXXX   .X.X.   .X.XX  |  XXX..   .XXXX   ...XX   .X.X.  |  X.+..   .....   .....   .....
.XX.X   XX...   X...X   .XX.X  |  .XX..   .XXXX   ...XX   .X.X.  |  .....   .....   .....   .....
X.XXX   X..XX   ..X..   ..X.X  |  .XX..   .XXXX   ...XX   .X.X.  |  .....   .....   .....   .....
                                  OOO-O   -OOOO   ---OO   -O-O-
Round 1 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
....X   .....   .....   .....  |  .....   .....   .....   X....  |  .....   .....   .....   X....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
X.+..   .....   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   X....  |  .....   .....   .....   X....
                                  -----   -----   -----   -----

3-round linear trail of total weight 20
* Profile related to χ:
Propagation weights:    8   8   4
Active rows:            4   4   2
* Profile related to θ:
Gaps:      5   0   0
Kernel:    N   k   k
Previous round would have weight at least 38
Round 0 (weight 8) after previous χ, then before θ of gap 5, then before χ (4 active rows):
..X.X   .X...   XX...   XXX.X  |  ..X..   .X...   XX.X.   XXXX.  |  .....   ..X..   .....   .....
X....   ...X.   ..XXX   X.XXX  |  ..X..   XXX..   XX.X.   XXXX.  |  .....   X....   .....   .....
XXX..   .XX..   ...X.   XXXX.  |  ..X..   .XX..   XX.X.   XXXX.  |  ..+..   .....   .....   .....
XX.XX   XX.XX   XX.XX   .....  |  ..XX.   .XX..   XX.X.   XXXX.  |  ...X.   .....   .....   .....
..XXX   ..XXX   .XX..   .X.X.  |  ..X..   ..X..   XX.X.   XXXX.  |  .....   .X...   .....   .....
                                  --OO-   O----   OO-O-   OOOO-
Round 1 (weight 8) after previous χ, then before θ of gap 0, then before χ (4 active rows):
.....   ..X..   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   X....   .....   .....  |  .....   X....   .....   .....  |  .....   X....   .....   .....
..+..   .....   .....   .....  |  ..+X.   .....   .....   .....  |  ..+X.   .....   .....   .....
...X.   .....   .....   .....  |  .....   X....   .....   .....  |  .....   X....   .....   .....
.....   .X...   .....   .....  |  ...X.   .....   .....   .....  |  ...X.   .....   .....   .....
                                  -----   -----   -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   X....   .....   .....  |  ..XX.   .....   .....   .....  |  ..XX.   .....   .....   .....
..+X.   .....   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   X....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
...X.   .....   .....   .....  |  ..XX.   .....   .....   .....  |  ..XX.   .....   .....   .....
                                  -----   -----   -----   -----

4-round linear trail of total weight 38
* Profile related to χ:
Propagation weights:   16   8   6   8
Active rows:            8   4   3   3
* Profile related to θ:
Gaps:      4   1   0   0
Kernel:    N   N   k   k
Previous round would have weight at least 40
Round 0 (weight 16) after previous χ, then before θ of gap 4, then before χ (8 active rows):
..X.X   ....X   XX.X.   ..X.X  |  X.X.X   .....   XX.X.   X..X.  |  .....   .....   .....   .....
XXX..   .X...   ..XX.   ..X.X  |  X.XXX   ..X..   XX.X.   X..X.  |  ...X.   ..X..   .....   .....
XXXX.   X....   .X.X.   X..XX  |  X.X.X   .....   X..X.   X..X.  |  ..+..   .....   .X...   .....
XX...   .X.XX   ..XX.   ...X.  |  XXX.X   .....   XX.X.   X..XX  |  .X...   .....   .....   ....X
.X.XX   ...XX   .X...   XX...  |  X...X   .....   XX...   X.XX.  |  ..X..   .....   ...X.   ..X..
                                  OO-OO   --O--   O----   O-OOO
Round 1 (weight 8) after previous χ, then before θ of gap 1, then before χ (4 active rows):
.....   .....   .....   .....  |  .X...   .....   ..X..   .....  |  .....   .....   .....   .....
...X.   ..XXX   .....   .....  |  .X...   .X...   ..X..   .....  |  .....   .X...   .....   .....
..+..   .....   .XX..   .....  |  .X+..   XX...   ..X..   .....  |  ..+..   XX...   .....   .....
.X...   .....   .....   X...X  |  .X...   .....   ...X.   .....  |  .....   .....   ..XX.   .....
..X..   .....   ...X.   ..X..  |  .....   .....   ..X..   .....  |  .X...   .....   .....   .....
                                  -----   O----   ---O-   -----
Round 2 (weight 6) after previous χ, then before θ of gap 0, then before χ (3 active rows):
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   X....   .....   .....  |  ..+.X   .....   .....   .....  |  ..+.X   .....   .....   .....
.....   .....   ..X..   .....  |  X...X   .....   .....   .....  |  X...X   .....   .....   .....
.X...   .....   .....   .....  |  X....   .....   .....   .....  |  X....   .....   .....   .....
                                  -----   -----   -----   -----
Round 3 (weight 8) after previous χ, then before θ of gap 0, then before χ (3 active rows):
.....   .....   .....   .....  |  .....   .X..X   .....   .....  |  .....   .X..X   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+.X   .....   .....   .....  |  ..+..   .X...   .....   .....  |  ..+..   .X...   .....   .....
....X   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
X.X..   .....   .....   .....  |  .....   ....X   .....   .....  |  .....   ....X   .....   .....
                                  -----   -----   -----   -----

5-round linear trail of total weight 66
* Profile related to χ:
Propagation weights:   12   8   4  22  20
Active rows:            6   2   2  10   8
* Profile related to θ:
Gaps:      6   0   0   2   0
Kernel:    N   k   k   N   k
Previous round would have weight at least 42
Round 0 (weight 12) after previous χ, then before θ of gap 6, then before χ (6 active rows):
XXXXX   ..XX.   X.XX.   ..X..  |  .X.XX   ...X.   ..XXX   X..XX  |  X....   .....   .X...   .....
XXXX.   XX.XX   X..X.   XXX..  |  XX.XX   .X.X.   .XXXX   X..XX  |  .....   .X...   .....   .....
.X+X.   X..XX   .XXXX   ...XX  |  XX+XX   ...X.   ..XXX   X..XX  |  ..+..   .....   .X...   .....
.XX..   .XX..   .XXX.   XX.XX  |  XX.XX   X..X.   .XXXX   X..XX  |  .....   X....   .....   .....
.X..X   XX..X   X..XX   XXX.X  |  XX.XX   ...X.   .XXXX   ...XX  |  .....   .....   .....   X....
                                  -O-OO   OO-O-   -OOOO   ---OO
Round 1 (weight 8) after previous χ, then before θ of gap 0, then before χ (2 active rows):
X....   .....   .X...   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .X...   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   X....   .....   .....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
.....   .....   .....   X....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
                                  -----   -----   -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   .....   .....   .....  |  .....   .X...   .....   .....  |  .....   .X...   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .....   .....  |  ..+..   .X...   .....   .....  |  ..+..   .X...   .....   .....
....X   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..X..   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
                                  -----   -----   -----   -----
Round 3 (weight 22) after previous χ, then before θ of gap 2, then before χ (10 active rows):
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
..+..   .X...   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .XX..  |  .....   .....   ..XX.   X.X..
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
                                  -----   -----   -----   -OO--
Round 4 (weight 20) after previous χ, then before θ of gap 0, then before χ (8 active rows):
.....   .....   ..X..   X.X..  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .....   ..X..   X....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   ..X..   X....  |  ..+.X   ...X.   X.XX.   .X...  |  ..+.X   ...X.   X.XX.   .X...
.....   .....   ..X..   XX...  |  .....   ...X.   .....   .....  |  .....   ...X.   .....   .....
.....   .....   ..X..   X....  |  ....X   .....   X.XX.   .X...  |  ....X   .....   X.XX.   .X...
                                  -----   -----   -----   -----

6-round linear trail of total weight 94
* Profile related to χ:
Propagation weights:   12   8   4  22  20  28
Active rows:            6   2   2  10   8  12
* Profile related to θ:
Gaps:      6   0   0   2   0   1
Kernel:    N   k   k   N   k   N
Previous round would have weight at least 42
Round 0 (weight 12) after previous χ, then before θ of gap 6, then before χ (6 active rows):
XXXXX   ..XX.   X.XX.   ..X..  |  .X.XX   ...X.   ..XXX   X..XX  |  X....   .....   .X...   .....
XXXX.   XX.XX   X..X.   XXX..  |  XX.XX   .X.X.   .XXXX   X..XX  |  .....   .X...   .....   .....
.X+X.   X..XX   .XXXX   ...XX  |  XX+XX   ...X.   ..XXX   X..XX  |  ..+..   .....   .X...   .....
.XX..   .XX..   .XXX.   XX.XX  |  XX.XX   X..X.   .XXXX   X..XX  |  .....   X....   .....   .....
.X..X   XX..X   X..XX   XXX.X  |  XX.XX   ...X.   .XXXX   ...XX  |  .....   .....   .....   X....
                                  -O-OO   OO-O-   -OOOO   ---OO
Round 1 (weight 8) after previous χ, then before θ of gap 0, then before χ (2 active rows):
X....   .....   .X...   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .X...   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   X....   .....   .....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
.....   .....   .....   X....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
                                  -----   -----   -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   .....   .....   .....  |  .....   .X...   .....   .....  |  .....   .X...   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .....   .....  |  ..+..   .X...   .....   .....  |  ..+..   .X...   .....   .....
....X   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..X..   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
                                  -----   -----   -----   -----
Round 3 (weight 22) after previous χ, then before θ of gap 2, then before χ (10 active rows):
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
..+..   .X...   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .XX..  |  .....   .....   ..XX.   X.X..
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
                                  -----   -----   -----   -OO--
Round 4 (weight 20) after previous χ, then before θ of gap 0, then before χ (8 active rows):
.....   .....   ..X..   X.X..  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .....   ..X..   X....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   ..X..   X....  |  ..+.X   ...X.   X.XX.   .X...  |  ..+.X   ...X.   X.XX.   .X...
.....   .....   ..X..   XX...  |  .....   ...X.   .....   .....  |  .....   ...X.   .....   .....
.....   .....   ..X..   X....  |  ....X   .....   X.XX.   .X...  |  ....X   .....   X.XX.   .X...
                                  -----   -----   -----   -----
Round 5 (weight 28) after previous χ, then before θ of gap 1, then before χ (12 active rows):
.....   .....   .....   .....  |  ...X.   ....X   .X.XX   .....  |  ...X.   ...XX   XX.XX   .....
.....   .....   .....   .....  |  .....   ...X.   X.XX.   .....  |  .....   .....   ..XX.   .....
..+.X   ...XX   ...X.   .XX..  |  ..+..   .....   .....   ..X..  |  ..+..   ...X.   X....   ..X..
.....   ...XX   .....   .....  |  X....   .X...   X....   X....  |  X....   .X.X.   .....   X....
XX..X   .....   .X.XX   .X...  |  .....   ....X   .....   .....  |  .....   ...XX   X....   .....
                                  O--O-   -O-O-   -OO-O   O-O--

